本博客从入门级到 Ynoi 全覆盖 (确信),欢迎评论、点赞、转发!(日常营销号)
如果以下内容有错误,欢迎指出!转载全文或部分前请先联系作者。
同步发布于洛谷博客。
0x1 分块&块状数组
分块,顾名思义,就是将原数列分成若干块(一般取 左右,可以动态也可以取常数),进行的快速统计的方法。块状数组类似于线段树,维护区间的信息。
例题 1:P3372 【模板】线段树 1
(好好写线段树它不香吗)
由于块状数组的复杂度不正确,不保证此做法能在任意时刻通过此题,仅以此题为例讲解思路。
我们将原数列分成块长为 的若干个块,对于每一块,我们记录一个块内的和和一个懒标记。修改时,若左右端点在同一块,直接暴力修改原数组和分块;若不在同一块,暴力修改左右零散块,中间整块修改块内的和以及懒标记。查询时类似,记得懒标记下放。
时间复杂度为 。
容易写出代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5, SIZE = 320, K = 320;
ll n, m, a[N], s[K], tag[K], L[K], R[K], tot;
#define whichBlock(x) (\
(x-1)/SIZE+1\
)
void initBlock() {
tot = whichBlock(n);
for(ll i=1;i<=tot;i++) {
L[i] = R[i-1] + 1;
R[i] = i * SIZE;
for(ll j=L[i];j<=min(R[i],n);j++) s[i] += a[j];
}
R[tot] = n;
}
void pushdown(ll u) {
ll X = whichBlock(u);
if(!tag[X]) return;
for(ll i=L[X];i<=R[X];i++) a[i] += tag[X];
tag[X] = 0;
}
void modify(ll l, ll r, ll k) {
ll X = whichBlock(l), Y = whichBlock(r);
if(X == Y) for(ll i=l;i<=r;i++) a[i] += k, s[X] += k;
else {
for(ll i=l;i<=R[X];i++) a[i] += k, s[X] += k;
for(ll i=X+1;i<Y;i++) tag[i] += k, s[i] += (R[i] - L[i] + 1) * k;
for(ll i=L[Y];i<=r;i++) a[i] += k, s[Y] += k;
}
}
ll query(ll l, ll r) {
ll X = whichBlock(l), Y = whichBlock(r), ans = 0;
if(X == Y) {
pushdown(l);
for(ll i=l;i<=r;i++) ans += a[i];
}
else {
pushdown(l);
for(ll i=l;i<=R[X];i++) ans += a[i];
for(ll i=X+1;i<Y;i++) ans += s[i];
pushdown(r);
for(ll i=L[Y];i<=r;i++) ans += a[i];
}
return ans;
}
int main() {
scanf("%lld%lld", &n, &m);
for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
initBlock();
while(m--) {
ll op, l, r, x;
scanf("%lld%lld%lld", &op, &l, &r);
if(op == 1) {
scanf("%lld", &x);
modify(l, r, x);
}
else printf("%lld\n", query(l, r));
}
return 0;
}
【完结撒花!】
其实分块大概就是这样,基础部分练习完了,我们来看几道习题。
部分习题有题解,不做额外讲解;其他的大概提思路。
习题 1:P5309 [Ynoi2011]初始化 | 题解
习题 2:P5356 [Ynoi2017]由乃打扑克 | 题解
0x2 莫队
例题 1:P1972 [SDOI2009]HH的项链
不过这题好像把莫队卡了,那就好好用树状数组吧。
没关系,我们有双倍经验。
例题 1.5:SP3267 DQUERY - D-query
统计区间内颜色个数,怎么办呢?
我们考虑暴力。每次暴力统计一遍太费时间了,我们搞两个指针,表示当前统计到的区间,然后在用一个数组存每个颜色在区间内有多少个,一个变量存区间内有多少颜色即可。统计到下一个区间,我们移动这两个指针(实时更新数组内的值),通过上面提到的数组来更新变量(颜色)的值。
但是这样很容易被卡:询问 效率明显低下。怎么办呢?离线做法,先对询问进行排序!
排序的伪代码:
结构体 Query {int l, r, id;}
比较(Query a, Query b):
如果 a.l 与 b.l 在同一块中:
比较 a.r 与 b.r 并返回
否则:
比较 a.l 与 b.l 并返回
在排序后,这个算法的效率是更高的,可以算出复杂度为 。
(写作时间紧张,复杂度证明先咕了,改天再加)
例题 2:P2709 小B的询问
统计区间内不同数的个数的平方和,与上面类似,采用莫队。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+5, SIZE = 250;
int n, m, k, a[N], tot, s[N], ans[N];
#define whichBlock(x) (\
(x-1)/SIZE+1\
)
struct Node {
int l, r, id;
friend bool operator < (const Node &a, const Node &b) { // 排序方法
int x = whichBlock(a.l), y = whichBlock(b.l);
if(x == y) return a.r < b.r;
return x < y;
}
}q[N];
void modify(int x, int y) { // 莫队指针移动更新数据
int z = a[x];
tot -= s[z] * s[z];
s[z] += y;
tot += s[z] * s[z];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
for(int i=1;i<=m;i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q+1, q+1+m);
int l = 1, r = 0;
for(int i=1;i<=m;i++) {
while(l < q[i].l) modify(l++, -1); // 移动指针
while(l > q[i].l) modify(--l, 1);
while(r < q[i].r) modify(++r, 1);
while(r > q[i].r) modify(r--, -1);
ans[q[i].id] = tot;
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}
习题 1:P1494 [国家集训队]小Z的袜子
小Z的妹子袜子这题需要一定的数学推导,和上面那题类似,也需要维护区间平方和。
习题 2:P4688 [Ynoi2016]掉进兔子洞 | 题解
用 bitset 套莫队即可。
完结撒花!
带修莫队和树上莫队因为自己还没做所以先不写了,以后会写新博客更新的~
(话说我这么用 Ynoi 当习题会不会被打)